In prior art, encoding into what are called turbo-codes has been performed to efficiently transmit data. FIG. 1 shows one example of the configuration of a turbo-encoder which performs turbo-encoding on the transmission side. The input data is supplied as systematic bits to a parallel/serial converter 11, and are supplied to a first convolutional encoder 20, as well as to a second convolutional encoder 30 through an interleaver 12. The first convolutional encoder 20 uses adders 21 and 25, and D flip-flops 22, 23, and 24 to perform convolution processing to generate parity bits a, and the generated parity bits a are supplied to the parallel/serial converter 11. The second convolutional encoder 30 uses adders 31 and 35, and D flip-flops 32, 33, and 34 to perform convolution processing to generate parity bits b, and the generated parity bits b are supplied to the parallel/serial converter 11.
The parallel/serial converter 11 converts the supplied systematic bits and parity bits a and b into serial data in a predetermined order, and outputs the result as turbo-encoded data.
On the side receiving a transmitted signal which has been turbo-encoded in this way, decoding is performed using, for example, a turbo-decoder shown in FIG. 2. To explain the configuration of the turbo-decoder shown in FIG. 2, the received signal is supplied to a serial/parallel converter 41, and is separated to be systematic bits and parity bits a and b. Separation by this serial/parallel converter 41 is executed with timing indicated by a timing control circuit 49.
A soft output decoding algorithm unit 42 uses the separated systematic bits, the parity bits a, and the output signal of a memory 46 for deinterleaving to perform decoding processing using a soft output decoding algorithm called a MAP algorithm. Data decoded in the soft output decoding algorithm unit 42 is supplied to a memory 43 for interleaving and is subjected to interleaving processing; and then the interleaved data and parity bits b separated in the serial/parallel converter 41 are supplied to a soft output decoding algorithm unit 44. Decoding processing using the MAP algorithm is also performed by the soft output decoding algorithm unit 44, and the decoded output is supplied, through the deinterleave memory 46, to the soft output decoding algorithm unit 42. Hence the outputs of decoding processing in the soft output decoding algorithm unit 42 and of decoding processing in the soft output decoding algorithm unit 44 are supplied to each other to perform iterative decoding.
Data which has been interleaved in the interleave memory 43 and the decoded output of the soft output decoding algorithm unit 44 are supplied to an adder 45 and added, and the added output is supplied to a hard decision unit 47. The hard decision unit 47 is a circuit which obtains the final decoding result. The result of decision (decoding) in this hard decision unit 47 is supplied to the deinterleave memory 48 and is subjected to deinterleaving, and the deinterleaved data is output as the result of decoding of the turbo-code.
The timing of processing is supplied to each of the soft output decoding algorithm units 42 and 44, and to the interleave memory 43, deinterleave memory 46, and deinterleave memory 48 by the timing control circuit 49.
To explain the decoding processing states of the turbo-decoder shown in FIG. 2, since a turbo-code is a block code, encoding processing and decoding processing are performed in units of blocks including a stipulated number of bits N. These block units are here called code blocks. The required numbers of words held by the interleave memory and deinterleave memory are equal to the number of bits in one code block.
The iterative decoding performed by the two soft output decoding algorithm units 42 and 44 is iterated, for example, from several times to several tens of times. Prior to beginning iterative decoding, the soft output decoding algorithm unit 42 is initialized to an initial value (0). To explain in summary the processing of one cycle of this iterative decoding, in the first half of the first cycle, the soft output decoding algorithm unit 42 operates. The systematic bits, parity bits a, and output of the deinterleave memory 46 are output to the soft output decoding algorithm unit 42. The output of the soft output decoding algorithm unit 42 is accumulated in the interleave memory 43. At the time of the first cycle of iterative processing, no information has yet been accumulated in the deinterleave memory 46, and so the initial value (0) is also used therein.
In the second half of the first cycle, the soft output decoding algorithm unit 44 operates. The parity bits b and output of the interleave memory 43 are supplied to the soft output decoding algorithm unit 44. In this configuration, the systematic bits corresponding to the MAP algorithm b decoded in the soft output decoding algorithm unit 44 are not transmitted, and 0 is input. The decoded output of this soft output decoding algorithm unit 44 is accumulated in the deinterleave memory 46. The above summarizes the first cycle of decoding processing in the iterative decoding processing. Information sent to the soft output decoding algorithm units 44 and 42 from the interleave memory 43 and deinterleave memory 46 is called prior likelihood information.
After this processing cycle is repeated a predetermined number of times, the hard decision result (sign bit) of the output added by the adder 45 is obtained in the hard decision unit 47, this result is supplied to the deinterleave memory 48, and the bit sequence is restored to obtain the final decoding result.
Next, operation of the MAP algorithm used in decoding processing in the soft output decoding algorithm units 42 and 44 is explained, referring to FIG. 3. This MAP algorithm is explained in a paper by L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optical Decoding of Linear Codes for Minimizing Symbol Error Rate”, IEEE Transactions on Information Theory, Vol. IT-20, March 1974, pp. 284–7.
In a MAP algorithm, soft decision output is obtained for each bit position in a code block. At this time, recursive operations in the forward and inverse directions are necessary to determine the state metric on the trellis. As indicated in FIG. 3, this processing must be executed continuously, in single-block units, from beginning to end. That is, after storing the state metric for each state through recursive operations throughout an N-stage code block, processing must be performed. In order to perform such processing, memory capable of storing large amounts of data is necessary. For example, in the case of processing (code block length N to 5114, number of states M=8) applied to a wireless telephone system called W-CDMA, the required memory capacity is as large as approximately 40 k words.
Therefore, as techniques to reduce the amount of memory required by MAP algorithms, processing using a sliding window has been proposed in reference 1 and reference 2.
[Reference 1] A paper by S. Pietrobon and S. Barbulescu, “A Simplification of the Modified Bahl et al. Decoding Algorithm for Systematic Convolutional Codes”, Int. Symp. On Inform. Theory and Its Applications, Sydney, Australia, pp. 1073–7, November 1994, revised Jan. 4, 1996.
[Reference 2] A paper by S. Pietrobon, “Efficient Implementation of Continuous MAP Decoders and a Synchronization Technique for Turbo Decoders”, Int. Sym. On Inform Theory and Its Applications, Victoria, B. C., Canada, pp. 586–9, September 1996.
Details of the above-described decoding processing using a sliding window are explained in an embodiment of this invention, however in brief, recursive operations are executed in window units. If the window length is L and the time of a certain window is t, then a inverse-direction recursive operation begins from time t+2L, and the state metric resulting from the inverse-direction recursive operation is stored in memory over the interval from time t+L to time t.
The interval from time t+2L to time t+L is here called a learning interval, because processing is performed to adequately improve the reliability of recursive operations divided in window units. If the length of the learning interval is P, then in the above non-patent reference it is stated that P=L; however this is not necessarily the case. By shortening the length P of the learning interval, increases in the volume of operations can be suppressed, however on the other hand there is degradation of performance; hence the value of P must be decided with care, and it has been necessary to provide a certain margin. Forward-direction recursive operations and output likelihood calculations are executed in the interval from time t to time t+L.
Similar processing is performed for the next window, with the leading position of the window increased by L to t+L. Processing is subsequently continued, increasing (sliding) the leading position of the window by L each time, until the end of the trellis is reached. A learning interval is not provided for recursive operations performed from the end of the trellis.
By performing operations using such a sliding window, the required amount of memory is reduced from N*M words to L*M words. However, with respect to the volume of operations, the volume of inverse-direction recursive operations is increased by a factor of 2.
In this way, the length P of the learning interval is determined taking into account the allowable increase in the volume of operations and the degradation in performance. In order to reduce the volume of operations, the length of the learning interval must be shortened; however, depending on the state of the turbo-codes transmitted, an appropriate learning interval length may not always be set.
The present invention was devised in light of the above considerations, and has as an object of providing a data reception method and device in which, when turbo-codes are received and decoding is performed through operations using a sliding window, the length of the learning interval can be set optimally.